package com.practice.niuke.new_direct_practice.class09;

import java.util.HashMap;

/**
 * 设计LRU缓存结构， 该结构在构造时确定大小， 假设大小为K， 并有如下两个功能。
 * set(key,value):将记录(key,value)插入该结构。 get(key):返回key对应的value值。
 * 【要求】
 * 1.set和get方法的时间复杂度为O(1) 2.某个key的set或get操作一旦发生， 认为这个key的记
 * 录成了最常使用的 3.当缓存的大小超过K时， 移除最不经常使用的记录， 即set或get最久远的
 * 【举例】
 * 假设缓存结构的实例是cache， 大小为3， 并依次发生如下行为 1.cache.set("A",1)。 最常使
 * 用的记录为("A",1) 2.cache.set("B",2)。 最常使用的记录为("B",2)， ("A",1)变为最不常使
 * 用的 3.cache.set("C",3)。 最常使用的记录为("C",2)， ("A",1)还是最不常使用的
 * 4.cache.get("A")。 最常使用的记录为("A",1)， ("B",2)变为最不常使用的
 * 5.cache.set("D",4)。 大小超过了3， 所以移除此时最不常使用的记录("B",2)， 加入记录
 * ("D",4)， 并且为最常使用的记录， 然后("C",2)变为最不常使用的记录。
 */
public class Code01_LeastRecentlyUsedCache {

	/**
	 * 双向链表的节点类型
	 *
	 * @param <K> key的类型
	 * @param <V> value的类型
	 */
	public static class Node<K, V> {
		public K key;
		public V value;
		// 指向前一个节点的指针
		public Node<K, V> last;
		// 指向后一个节点的指针
		public Node<K, V> next;

		public Node(K key, V value) {
			this.key = key;
			this.value = value;
		}
	}

	/**
	 * 我们自己实现的双向链表结构，
	 * 注意点（潜台词）：从 head 到 tail 所有节点都是串好的
	 *
	 * @param <K>
	 * @param <V>
	 */
	public static class NodeDoubleLinkedList<K , V> {

		// 双向链表的头指针
		private Node<K, V> head;
		// 双向链表的尾指针
		private Node<K, V> tail;

		// 初始化一个空的双向链表
		public NodeDoubleLinkedList() {
			this.head = null;
			this.tail = null;
		}

		/**
		 * 如果一个新的节点加入，放到我们这个双向链表的尾巴上去
		 *
		 * @param newNode 待加入的节点
		 */
		public void addNode(Node<K, V> newNode) {
			if (newNode == null) {
				// 如果待加入的节点是null，认为是非法值，啥也不做。
				return;
			}
			// newNode != null
			if (this.head == null) {
				// this.head == null 说明：此时双向链表中一个节点也没有，
				// 加入的这个待加入的节点后，head 和 tail 都指向这个新节点。
				this.head = newNode;
				this.tail = newNode;
			} else {
				// 否则，双向链表中之前有节点，意味着 tail 非null，让：
				// （1）之前的tail的next指针指向新的节点，
				// （2）新节点的last指针（向前的指针）指向之前的tail，
				// （3）让tail指向新的节点
				this.tail.next = newNode;
				newNode.last = this.tail;
				this.tail = newNode;
			}
		}

		/**
		 * 将双向链表中的某一个节点移动到双向链表为尾部去。
		 * 潜台词 ：
		 * （1）双向链表上一定有这个node；
		 * （2）node 分离出，但是node前后环境重新连接；
		 * （3）node 放到尾巴上去
		 *
		 * @param node 待移动的节点
		 */
		public void moveNodeToTail(Node<K, V> node) {
			if (this.tail == node) {
				// 待移动的节点已经在双向链表的尾部上，啥也不用干
				return;
			}
			if (this.head == node) {// 当前待移动的 node 是老头部，
				// （1）让head指向node的下一个节点，
				this.head = node.next;
                // （2）让新的head的last指针（向前的指针）指向null
				this.head.last = null;
			} else {
				// 当前待移动的node是双向链表的中间的一个节点，
				// （1）让 当前node的last指针指向的节点 的next指针 指向 当前node的next指针指向的节点，
				// （2）让 当前node的next指针指向的节点 的last指针 指向 当前node的last指针指向的节点
				node.last.next = node.next;
				node.next.last = node.last;
			}
			// （3）让当前node的last指针（指向前的指针）指向tail，
			node.last = this.tail;
			// （4）让当前node的next指针指向null，
			node.next = null;
			// （5）让当前的tail的next指针指向当前node，
			this.tail.next = node;
			// （6）让tail指针指向当前节点
			this.tail = node;
		}

		/**
		 * 删除该双向链表的头节点，并且返回
		 *
		 * @return Node<K, V>
		 */
		public Node<K, V> removeHead() {
			if (this.head == null) {
			    // 如果head == null 说明一个节点也没有，返回null
				return null;
			}
			// 拿到此时的头节点，最后用作返回值
			Node<K, V> res = this.head;
			if (this.head == this.tail) { // 链表中只有一个节点的时候
				this.head = null;
				this.tail = null;
			} else {
			    // 让头节点指向此时头节点的next指针指向的节点
				this.head = res.next;
				// 让老的头节点的next指针指向null
				res.next = null;
				// 让新的头节点的last指针（指向前的指针）指向null
				this.head.last = null;
			}
			// 返回老的头节点
			return res;
		}

	}

	/**
	 * 我们实现LRU算法的结构（TODO：标记重点，起始代码读取位置）
	 *
	 * @param <K> 键的类型
	 * @param <V> 值的类型
	 */
	public static class MyCache<K, V> {
		// HashMap, 该map的key的类型为K类型，该map的value的类型为Node<K, V>类型
		private HashMap<K, Node<K, V>> keyNodeMap;
		// 我们自己实现的双向链表结构
		private NodeDoubleLinkedList<K, V> nodeList;
		// capacity：容量达到多少的时候删除最少使用的记录
		private final int capacity;

		public MyCache(int capacity) {
			if (capacity < 1) {
				throw new RuntimeException("should be more than 0.");
			}
			this.keyNodeMap = new HashMap<K, Node<K, V>>();
			this.nodeList = new NodeDoubleLinkedList<K, V>();
			this.capacity = capacity;
		}

		/**
		 * 查询key对应的Value
		 *
		 * @param key
		 * @return
		 */
		public V get(K key) {
			if (this.keyNodeMap.containsKey(key)) {// map中有k的记录
			    // 在map中拿到key记录的 Node<K, V> res 值
				Node<K, V> res = this.keyNodeMap.get(key);
				// 将这个key对应的这个Node<K, V> res 值所指向的节点，移动到双端链表的末尾
				this.nodeList.moveNodeToTail(res);
				// 返回拿到的这个res值
				return res.value;
			}
			return null;
		}

		/**
		 * 向当前这个结构中加入一条新记录，或修改已经存在的key对应的value
		 *
		 * @param key key
		 * @param value value
		 */
		public void set(K key, V value) {
			if (this.keyNodeMap.containsKey(key)) {// 修改已有的记录
			    // 在map中拿到key记录的 Node<K, V> node 值
				Node<K, V> node = this.keyNodeMap.get(key);
				// 更新拿到的这个 Node<K, V> node 的value为传入的value
				node.value = value;
				// 将这个key对应的Node<K, V> node所指向的节点，移动到双端链表的末尾
				this.nodeList.moveNodeToTail(node);
			} else { // 这是一个新加的记录，有可能出现替换
			    // 根据传入的key和value，生成一个Node<K, V> newNode
				Node<K, V> newNode = new Node<K, V>(key, value);
				// 向map中加入一条key对应的记录，key对对应的value值为Node<K, V> newNode
				this.keyNodeMap.put(key, newNode);
				// 将Node<K, V> newNode所代表的节点加入到双向链表的尾部
				this.nodeList.addNode(newNode);
				if (this.keyNodeMap.size() == this.capacity + 1) {// 新加入节点后发现容量超了
					this.removeMostUnusedCache();
				}
			}
		}

		/**
		 * 删除最少使用的一条记录
		 */
		private void removeMostUnusedCache() {
			Node<K, V> removeNode = this.nodeList.removeHead();
			this.keyNodeMap.remove(removeNode.key);
		}

	}

	public static void main(String[] args) {
		MyCache<String, Integer> testCache = new MyCache<String, Integer>(3);
		testCache.set("A", 1);
		testCache.set("B", 2);
		testCache.set("C", 3);
		System.out.println(testCache.get("B"));
		System.out.println(testCache.get("A"));
		testCache.set("D", 4);
		System.out.println(testCache.get("D"));
		System.out.println(testCache.get("C"));

	}

}
